🛒 Subset Sum for Grocery Shopping

Help Riya find items that exactly match her budget

👩‍💻 Riya's Grocery Challenge

🎯 The Mission:

Help Riya find a combination of grocery items that exactly matches her budget, or determine if no such combination exists.

📋 Requirements:

  • Compute (budget + 10) * 3 and print it first
  • Find a combination of item prices that sum to the budget
  • Handle 1 to 10 items, prices from 1 to 50, budget from 1 to 150
  • Output the first valid combination or "No combination of products"

Input/Output Specifications

  • Input: Integer n (number of items), n space-separated integers (prices), integer tbudget (budget)
  • Output: First line: (budget + 10) * 3; Second line: space-separated prices or "No combination of products"

Example: prices = [2, 4, 6, 10, 3], budget = 13

Prices:

2
4
6
10
3

Output: 69
4 6 3

Example: prices = [5, 8, 12, 20], budget = 7

5
8
12
20

Output: 51
No combination of products

⚡ Subset Sum Explained

How Subset Sum Works

  1. Dynamic Programming: Use a DP table where dp[i][j] indicates if a sum j is possible with the first i items
  2. Fill Table: For each item and sum, decide whether to include the item or not
  3. Backtrack: Trace back to find the selected items if a solution exists

DP Table Example (prices = [2, 4, 6], budget = 12)

Price \ Sum0123456789101112
0TFFFFFFFFFFFF
2TFTFFFFFFFFFF
4TFTFTFTFFFFFF
6TFTFTFTFTFTFT

Solution: [6, 6] sums to 12

Time Complexity

O(n * budget)

For filling the DP table

Space Complexity

O(n * budget)

For DP and path tables

Why Subset Sum?

  • ✅ Solves budget allocation problems
  • ✅ Finds exact combinations efficiently
  • ✅ Applicable in knapsack-like scenarios
  • ❌ Large budgets increase space usage

🔍 Step-by-Step Subset Sum Demo

Click "Start Demo" to begin step-by-step visualization

Algorithm Progress:

1. Display input prices and budget
2. Build DP table
3. Backtrack and display result

Current Prices:

DP Table (Price \ Sum):

🎮 Practice Subset Sum

Enter prices and budget, then click "Find Combination"

Test Cases

Example 1: prices = [2, 4, 6, 10, 3], budget = 13 → 69
4 6 3

Example 2: prices = [5, 8, 12, 20], budget = 7 → 51
No combination of products

📊 Algorithm Analysis

Subset Sum Process

  1. Compute Expression: Calculate (budget + 10) * 3
  2. Build DP Table: Fill dp[i][j] to check if sum j is possible with first i items
  3. Backtrack: If dp[n][budget] is true, trace back to find selected items
  4. Output: Print expression result, then the combination or "No combination of products"

Time Complexity

O(n * budget)

For filling the DP table

Space Complexity

O(n * budget)

For DP and path tables

Key Points

  • Dynamic Programming: Efficiently finds exact sum combinations
  • Backtracking: Retrieves the first valid combination
  • Applications: Budgeting, resource allocation
  • Limitation: Space-intensive for large budgets